A sparse signal refers to a signal which includes nonzero elements of which the number is equal to or smaller than K (K<<N), when the length of the signal is set to N. Compressed sensing is a signal compression processing method which is capable of significantly reducing the information amount of the sparse signal.
A transmitter generates a compressed-sensed measurement signal Y by linearly projecting a target sparse signal X to a measurement matrix A, and transmits the generated measurement signal Y. A receiver searches for a target sparse signal X which has the minimum number of nonzero elements among infinite solutions which satisfies Y=AX. Such a sparse signal recovery method may be simply expressed as the following equation. However, the sparse signal recovery method requires N searches to recover the target signal. Thus, when N and K are increased, the complexity of the method is exponentially increased.
            min      X        ⁢                          X                    0            subject    ⁢                  ⁢    to        AX    =    Y                              X                    0        :=          the      ⁢                          ⁢      number      ⁢                          ⁢      of      ⁢                          ⁢      nonzero      ⁢                          ⁢      elements      ⁢                          ⁢      in      ⁢                          ⁢      X      
In addition, the method for recovering a compressed-sensed signal may include an OMP (Orthogonal Matching Pursuit) method, a StOMP (Stagewise Orthogonal Matching Pursuit), and a basis pursuit method. However, such recovery methods are operated on the real number system, and have a limitation in recovering a sparse signal of a finite field.